/*
提交链接：https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/submissions/562815612
712. 两个字符串的最小ASCII删除和-中等
完成日期：2024/9/8
线性dp
*/

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        // 创建一个 (m+1) x (n+1) 的 DP 表格
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 初始化 DP 表格
        // 将 s1 的前 i 个字符删除成空字符串的代价
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = dp[i-1][0] + s1[i-1];
        }
        // 将 s2 的前 j 个字符删除成空字符串的代价
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = dp[0][j-1] + s2[j-1];
        }
        // 填充 DP 表格
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i-1] == s2[j-1]) {
                    // 如果字符相等，则不需要额外删除
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    // 取删除 s1[i-1] 或 s2[j-1] 的最小代价
                    dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
                }
            }
        }
        // 返回将 s1 和 s2 变得相等所需删除的最小 ASCII 代价
        return dp[m][n];
    }
};